package org.lql.algo.codecrush.week004;

import java.util.Stack;

/**
 * @author: liangqinglong
 * @date: 2025-08-01 17:52
 * @description: LCR 184. 设计自助结算系统 <a href="https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/description/">...</a>
 **/
public class Checkout {

	/**
	 * 请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：
	 * <p>
	 * get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1
	 * add(value)：将价格为 value 的商品加入待结算商品队列的尾部
	 * remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1
	 * 注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)
	 */

	private Stack<Integer> inStack = new Stack<>();
	private Stack<Integer> outStack = new Stack<>();
	private Stack<Integer> inMax = new Stack<>();
	private Stack<Integer> outMax = new Stack<>();

	public Checkout() {
	}

	public int get_max() {
		if (inMax.isEmpty() && outMax.isEmpty()) {
			return -1;
		}
		if (inMax.isEmpty()) {
			return outMax.peek();
		}
		if (outMax.isEmpty()) {
			return inMax.peek();
		}
		return Math.max(inMax.peek(), outMax.peek());
	}

	public void add(int value) {
		inStack.push(value);
		int max = inMax.isEmpty() ? value : Math.max(value, inMax.peek());
		inMax.push(max);
	}

	public int remove() {
		if (outStack.isEmpty()) {
			// 将 inStack 全部倒入 outStack，同时维护 outMax
			while (!inStack.isEmpty()) {
				int val = inStack.pop();
				inMax.pop();
				outStack.push(val);
				int max = outMax.isEmpty() ? val : Math.max(val, outMax.peek());
				outMax.push(max);
			}
		}
		if (outStack.isEmpty()) {
			return -1;
		}

		outMax.pop();
		return outStack.pop();
	}
}
